Kajaki

Limit pamięci: 32 MB

Organizując spływ, wypożyczamy na przystani kajaki. Wszystkie kajaki są jednakowe. W jednym kajaku mogą popłynąć co najwyżej dwie osoby, a suma ich wag nie może przekroczyć ustalonego maksymalnego obciążenia. Aby zapłacić jak najmniej, szukamy sposobu rozmieszczenia wszystkich uczestników spływu w minimalnej liczbie kajaków.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia maksymalne obciążenie kajaka, liczbę uczestników spływu i wagę każdego z nich,
• oblicza minimalną liczbę kajaków, jakie należy wynająć, aby rozmieścić w nich wszystkich uczestników spływu w zgodzie z przepisami,
• zapisuje wynik na standardowe wyjściem.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita , spełniająca nierówności . Jest to maksymalne obciążenie kajaka. W drugim wierszu jest zapisana jedna liczba całkowita , spełniająca nierówności . Jest to liczba uczestników spływu.

W każdym z kolejnych wierszy jest zapisana jedna liczba całkowita z przedziału . Jest to waga jednego uczestnika spływu.

Wyjście

W pierwszym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą — minimalną liczbę kajaków, jakie trzeba wynająć.

Przykład

Dla danych wejściowych:

100
9
90
20
20
30
50
60
70
80
90

poprawną odpowiedzią jest:

6

Autor zadania: Wojciech Rytter.